package Exp_2;

import java.util.ArrayDeque;
import java.util.Deque;

public class BiTree {
    BiTreeNode root;

    public BiTree() {
        this.root = null;
    }

    public BiTree(BiTreeNode root) {
        this.root = root;
    }

    static int index = 0;
    public BiTree(String preStr) {
        char c = preStr.charAt(index++);
        if (c!='#') {
            root = new BiTreeNode(c);
            root.lchild = new BiTree(preStr).root;
            root.rchild = new BiTree(preStr).root;
        } else
            root = null;
    }
    public void indexTo0(){
        index=0;
    }

    //先根遍历结果存入数组
    private int preToArray(BiTreeNode T, Object[] array, int pos) {
        if (T == null)
            return 0;
        array[pos++] = T.data;
        int countLeft = preToArray(T.lchild, array, pos);
        int countRight = preToArray(T.rchild, array, pos + countLeft);
        return countLeft + countRight + 1;
    }
    //从数组中取出先根遍历序列第k个元素
    public Object searchPre(BiTreeNode root,int k){
        Object[] array = new Object[100];//数组长度要大于等于序列长度
        int pos=0;
        preToArray(root,array,pos);
        return array[k-1];
    }
    //中根遍历结果存入数组
    private int inToArray(BiTreeNode T, Object[] array, int pos) {
        if (T == null)
            return 0;
        int countLeft = inToArray(T.lchild, array, pos);
        array[countLeft+pos++] = T.data;
        int countRight = inToArray(T.rchild, array, pos + countLeft);
        return countLeft + countRight + 1;
    }
    //从数组中取出中根遍历序列第k个元素
    public Object searchIn(BiTreeNode root,int k){
        Object[] array = new Object[100];//数组长度要大于等于序列长度
        int pos=0;
        inToArray(root,array,pos);
        return array[k-1];
    }
    //后根遍历结果存入数组
    private int postToArray(BiTreeNode T, Object[] array, int pos) {
        if (T == null)
            return 0;
        int countLeft = postToArray(T.lchild, array, pos);
        int countRight = postToArray(T.rchild, array, pos + countLeft);
        array[pos++] = T.data;
        return countLeft + countRight + 1;
    }
    //从数组中取出后根遍历序列第k个元素
    public Object searchPost(BiTreeNode root,int k){
        Object[] array = new Object[100];//数组长度要大于等于序列长度
        int pos=0;
        postToArray(root,array,pos);
        return array[k-1];
    }
    //判断是否是完全二叉树
    public boolean isCompleteTree() {
        if (root == null) {
            return true;
        }
        Deque<BiTreeNode> q = new ArrayDeque();
        q.offer(root);
        while (!q.isEmpty()) {
            BiTreeNode t = q.poll();
            if (t.lchild != null) {
                q.offer(t.lchild);
                if (t.rchild != null) {
                    q.offer(t.rchild);
                } else{
                    break;
                }
            } else if (t.rchild != null) {
                return false;
            }else
                break;
        }
        while (!q.isEmpty()) {
            // 判断队中剩余的节点是否都是叶子结点
            BiTreeNode t = q.poll();
            if (t.lchild != null || t.rchild != null) {
                return false;
            }
        }
        return true;
    }
}
